package com.algorithm.lesson_12;

import java.util.HashMap;
import java.util.Map;

/**
 * 最小包含子串的长度
 * 
 * @author Administrator
 *
 */
public class MinSubContainLen {
	// str1="abcde"， str2="ac"。 因为"abc"包含 str2 的所有字符，
	// 并且在满足这一条件的 str1 的所有子串中，"abc"是最短的， 返回 3。
	// str1="12345"， str2="344"。 最小包含子串不存在， 返回 0。

	/**
	 * 返回str1包含str2的短子串长度
	 * 
	 * @param str1
	 * @param str2
	 */
	public static int getMinSubContainLen(String str1, String str2) {
		if (str1.isEmpty() || str2.isEmpty()) {
			return 0;
		}

		Map<Character, Integer> map = new HashMap<>();

		char[] ch1 = str1.toCharArray();
		char[] ch2 = str2.toCharArray();
		int size = ch2.length;// 记录str2中的字符个数

		int i = 0;
		// 用一个map存储str2里面的字符，key:字符 value:字符对应个数
		while (i < size) {
			if (!map.containsKey(ch2[i])) {
				map.put(ch2[i], 1);
			} else {
				map.put(ch2[i], map.get(ch2[i]) + 1);
			}
			i++;
		}

		// 用两个指针来标记当前遍历窗口
		int left = 0;
		int right = 0;
		int count;
		int minLen = Integer.MAX_VALUE;// 最小值初始化为最大值

		// map中的value值指的是当前窗口中所需对应字符的数量
		// 例如{a：1,c:0}表示当前窗口[left,right]中还需1个a，0个c才能匹配
		while (right < ch1.length) {
			// right指针对str1进行遍历
			while (size != 0 && right < ch1.length) {
				if (map.containsKey(ch1[right])) {
					// map中包含当前字符
					count = map.get(ch1[right]);
					// 将对应字符的数量减一
					map.put(ch1[right], count - 1);
					if (count != 0)
						// 如果当前字符的数量已经为0，表示窗口不需要再匹配该字符则size不变，否则size--
						size--;
					size--;
				}
				right++;
			}
			while (size == 0) {
				int curLen = right - left;
				minLen = Math.min(minLen, curLen);
				if (map.containsKey(ch1[left])) {
					count = map.get(ch1[left]);
					map.put(ch1[left], count + 1);
					if (count == 0) {
						size++;
					}
				}
				left++;
			}
		}

		return minLen == Integer.MAX_VALUE ? 0 : minLen;
	}
}
